package com.ai.zuochengyun.phase01.class08;

/**
 * 暴力递归到动态规划
 * <p>
 * 机器人走路
 */
public class Code01_RobotWalk {

    public static void main(String[] args) {
        // 当前在什么位置   剩余要走的步数   目标位置   有1-4共四个位置可以走
        System.out.println(way1(2, 4, 4, 4));
        System.out.println(way2(2, 4, 4, 4));
        System.out.println(way3(2, 4, 4, 4));
    }

    /**
     * 走路的逻辑（暴力求解法）
     *
     * @param start 初始位置  变量
     * @param k     剩余要走的步数  变量，逐渐减少
     * @param aim   打算去的目标  固定值，不会改变
     * @param n     有哪些位置  固定值，不会改变
     * @return 可以达到目标的路的条数
     */
    public static int way1(int start, int k, int aim, int n) {
        return process1(start, k, aim, n);
    }

    /**
     * 四个参数的含义：
     *
     * @param cur  当前在什么位置
     * @param rest 剩余要走的步数
     * @param aim  目标位置
     * @param n    有1-4共四个位置可以走
     * @return
     */
    public static int process1(int cur, int rest, int aim, int n) {
        // 如果剩余步数为0，表示已经达到目标位置
        if (rest == 0) {
            // 如果当前的位置是目标位置，表明已经走到了目标位置，那么这条路就是可以到达的路
            return cur == aim ? 1 : 0;
        }

        // 为什么要rest - 1，因为到左 或者 到右，已经走了一步，所以，需要步数减一

        // rest > 0，表明还有步数要走
        // (cur, rest)坐标状态
        // 如果当前位置为1，只能往右边走  1 -> 2
        if (cur == 1) {
            return process1(2, rest - 1, aim, n);
        }

        // (cur, rest)坐标状态
        // 如果当前位置为n，只能往左边走  n-1 <- n
        if (cur == n) {
            return process1(n - 1, rest - 1, aim, n);
        }

        // 其余场合，说明当前位置在中间，既可以往左走，也可以往右走
        return process1(cur - 1, rest - 1, aim, n) + process1(cur + 1, rest - 1, aim, n);
    }

    /**
     * 走路的逻辑（使用动态规划改良版） 傻缓存法
     *
     * @param start 当前来到的位置  变量
     * @param k     剩余要走的步数  变量，逐渐减少
     * @param aim   打算去的目标  固定值，不会改变
     * @param n     有哪些位置  固定值，不会改变
     * @return 可以达到目标的路的条数
     */
    public static int way2(int start, int k, int aim, int n) {
        int[][] dp = new int[k + 1][n + 1];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(start, k, aim, n, dp);
    }

    /**
     * @param cur  的 范围在[1,n]
     * @param rest 的 范围在[0,k]
     * @param aim
     * @param n
     * @param dp
     * @return
     */
    public static int process2(int cur, int rest, int aim, int n, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }

        int ans = -1;
        // 如果剩余步数为0，表示已经达到目标位置
        if (rest == 0) {
            // 如果当前的位置是目标位置，表明已经走到了目标位置，那么这条路就是可以到达的路
            ans = cur == aim ? 1 : 0;
        }

        // 为什么要rest - 1，因为到左 或者 到右，已经走了一步，所以，需要步数减一

        // rest > 0，表明还有步数要走
        // (cur, rest)坐标状态
        // 如果当前位置为1，只能往右边走  1 -> 2
        else if (cur == 1) {
            ans = process2(2, rest - 1, aim, n, dp);
        }

        // (cur, rest)坐标状态
        // 如果当前位置为n，只能往左边走  n-1 <- n
        else if (cur == n) {
            ans = process2(n - 1, rest - 1, aim, n, dp);
        }

        // 其余场合，说明当前位置在中间，既可以往左走，也可以往右走
        else {
            ans = process2(cur - 1, rest - 1, aim, n, dp) + process2(cur + 1, rest - 1, aim, n, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

    /**
     * 记忆化搜索
     *
     * @param start 的 范围在[1,n]
     * @param k
     * @param aim
     * @param n
     * @return
     */
    public static int way3(int start, int k, int aim, int n) {
        // 通过可以移动的范围和要走的步数来构建一个dp数组，用来缓存计算过的结果
        // k对应剩余要走的步数，n表示可以走的位置范围
        // 横轴是对应rest，纵轴对应aim对应的位置
        int[][] dp = new int[k + 1][n + 1];
        // 怎么填数据，只要关注base，cur == target的时候，就填1，否则填0

        // 先初始化rest为0位置(第一列)的数据
        dp[aim][0] = 1;

        // 再初始化rest不为0位置的数据
        // 列
        // 同一列从上往下计算，先初始化第一行，然后执行中间行，最后计算最后一行
        for (int rest = 1; rest <= n; rest++) {
            // 当前位置在第一行的cur位置的时候，只依赖左下的位置
            dp[1][rest] = dp[2][rest - 1];

            // 既不是最上面的一行，也不是最下的一行
            for (int cur = 2; cur <= n - 1; cur++) {
                // 左上和左下的求和
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }

            // 当前位置在第一行的cur位置的时候，只依赖左上的位置
            dp[n][rest] = dp[n - 1][rest - 1];
        }

        // 开始的位置，走多少步
        return dp[start][k];
    }

}
